#include <queue>

using namespace std;

struct TreeNode
{
    TreeNode *left;
    TreeNode *right;
    int val;
    TreeNode(int x)
        : val(x), left(nullptr), right(nullptr)
    {
    }
};

class Solution
{
public:
    bool judge(int num, int level)
    {
        if (level % 2) //奇数层
        {
            if (num % 2 == 0)
            {
                return true;
            }
            return false;
        }
        else
        {
            if (num % 2)
            {
                return true;
            }
            return false;
        }
    }

    bool isEvenOddTree(TreeNode *root)
    {
        queue<TreeNode *> q;
        q.push(root);
        int num = 1, level = 0;
        while (!q.empty())
        {
            int next = 0;
            TreeNode *before = q.front();
            q.pop();
            if (!judge(before->val, level))
            {
                return false;
            }
            if (before->left)
            {
                q.push(before->left);
                ++next;
            }
            if (before->right)
            {
                q.push(before->right);
                ++next;
            }

            while (--num)
            {
                TreeNode *tmp = q.front();
                q.pop();
                if (tmp->left)
                {
                    q.push(tmp->left);
                    ++next;
                }
                if (tmp->right)
                {
                    q.push(tmp->right);
                    ++next;
                }

                if (judge(tmp->val, level))
                {
                    if (tmp->val % 2 == 0)
                    {
                        if (before->val <= tmp->val)
                        {
                            return false;
                        }
                    }
                    else
                    {
                        if (before->val >= tmp->val)
                        {
                            return false;
                        }
                    }
                }
                else
                {
                    return false;
                }
                before = tmp;
            }
            ++level;
            num = next;
        }
        return true;
    }
};